COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00029 00003	An NFA with finite alphabet $\Sigma$ and finite state set $Q$ is a labeled
C00032 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a13.tex[154,phy] \today\hfill}

\def\aot{\buildrel\rightarrow\over\otimes}%→  over \otimes 

\bigskip

\noindent{\bf String Axioms.}

An {\it alphabet\/} (usually called $\Sigma$) is a set, finite unless
otherwise stated, whose elements are called {\it characters\/}, or
occasionally symbols. {\it Strings\/} (over $\Sigma$) are finite
sequences of characters. The set of all strings over $\Sigma$ is
called~$\Sigma↑{\ast}$. A~physical realization of these definitions
must allow for distinguishing characters in all string contexts. The
axioms for strings are analogous to the Peano axioms for integers:

$$\vcenter{\halign{$\lft{#}\qquad$&\lft{#}\cr
\qquad\hbox{Integers}&\qquad Strings\cr
\noalign{\smallskip}
0\in N&\quad $\epsilon\in\Sigma↑{\ast}$\cr
&(the empty string $\epsilon$ is the empty sequence)\cr
x\in N⊃S(x)\in N&For each $a\in\Sigma$,\cr
&\quad $x\in\Sigma↑{\ast}⊃S↓a(x)\in\Sigma↑{\ast}$\cr
S(x)≠0&$S↓a(x)≠\epsilon$\cr
x≠y⊃S(x)≠S(y)&$x≠y⊃S↓a(x)≠S↓b(y)$\cr
&$a≠b⊃S↓a(x)≠S↓b(y)$\cr
\bigl(P(0)∧\bigl(\forall x.P(x)⊃P\bigl(S(x)\bigr)\bigr)\bigr)
&$P(\epsilon)∧\bigl(\forall x,a.P(x)⊃P\bigl(S↓a(x)\bigr)\bigr)$\cr
\qquad ⊃\forall x.P(x)&$\qquad ⊃\forall x\,P(x)$\cr
\noalign{\smallskip}
\hbox{I.e., there are no ``infinite''}&I.e., there are no ``infinite''\cr
\hbox{integers; all can be reached from}&strings.\cr
\hbox{zero in finitely many steps.}\cr}}$$

\smallskip
A {\it language\/} $L$ over $\Sigma$ is a subset of $\Sigma↑{\ast}$. It may
be empty, finite, infinite, etc. Languages over $\Sigma$ include~$\emptyset$,
the empty language; $\{\epsilon\}$,~the language containing only the
empty string, often abbreviated to~$\epsilon$ when no confusion can occur;
and $\Sigma↑{\ast}$ itself.

\vfill\eject

A {\sl relation\/} $R$ {\sl from\/} $S$ {\sl to\/} $T$ 
is a two-place predicate with domain $S\times T$.
If $S=T$, we call $R$ a relation {\sl on\/}~$S$. Normally, we write $uRv$ as
shorthand for $R(u,v)$. Familiar examples of relations are

$$\vcenter{\halign{$\ctr{#}$\quad&\lft{#}\quad&\lft{#}\cr
≤&&($S$ and $T$ the real numbers,\cr
&&or subsets thereof)\cr
\noalign{\smallskip}
=&&($S$ and $T$ can be any set)\cr
\noalign{\smallskip}
\subseteq&&($S$ and $T$ the power set of any set)\cr
\noalign{\smallskip}
\in&&($S$ any set, $T$ its power set)\cr
\noalign{\smallskip}
\equiv\,,\,\supset&&($S=T=\{\hbox{true},\hbox{false}\}$)\cr
\noalign{\smallskip}
|&(divides)&($S=$ the non-zero integers, $T=$ the integers)\cr
\noalign{\smallskip}
\approx&(is geometrically&($S=T=$ set of polygons)\cr
&congruent to)\cr
\noalign{\smallskip}
≡↓M&(differs by a multiple&($S=T=$ the integers)\cr
&of $M$ from)\cr
\tt{FATHER}&(short for&($S=T=$ the set of humans, living or dead)\cr
&``is the father of'')\cr
\hbox{\tt{MOTHER},}&(analogous)\cr
\hbox{\tt{BROTHER},}\cr
\hbox{\tt{WIFE}, etc.}\cr}}$$

The converse $R↑{-1}$ of such a relation is a relation from $T$ to~$S$,
where $vR↑{-1}u≡uRv$; converses of the relations above are respectively
$≥\,$, $=\,$, $\subseteq\,$, contains, $≡\,$, is implied by, is a multiple
of, $\approx\,$, $≡↓M\,$.

\smallskip
\disleft 38pt::
{\bf Drill:} What is the converse of {\tt WIFE}?

\smallskip
\disleft 38pt::
{\bf Drill:} Give a necessary and sufficient ({\sl nsuff\/}) condition
for $R$ to be its own converse.

\smallskip
\disleft 38pt::
{\bf Answer:} $S=T$, $(\forall x,y)(xRy\supset yRx)$.
Such a relation is called {\sl symmetric\/}. 

\smallskip
The composition $R=R↓1\circ R↓2$ of $R↓1$ (from $S↓0$ to~$S↓1$) with
$R↓2$ (from $S↓1$ to~$S↓2$) is a relation from $S↓0$ to~$S↓1$ defined by
$$uRw≡(\exists v\in S↓1)(uR↓1v\wedge vR↓2w)\,.$$

For example, the relation ``{\tt NEPHEW}'' is $\hbox{\tt son}\circ\hbox{\tt sibling}$,
and ``{\tt UNCLE}'' is $\hbox{\tt brother}\circ\hbox{\tt parent}$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(R↓1\circ R↓2)↑{-1}=R↓2↑{-1}\circ R↓1↑{-1}$.

\smallskip
\disleft 38pt::
{\bf Answer:} 
$$\eqalign{u(R↓1\circ R↓2)↑{-1}v&≡v(R↓1\circ R↓2)u
≡(\exists w)(vR↓1w\wedge wR↓2u)\,;\cr
\noalign{\smallskip}
u(R↓2↑{-1}\circ R↓1↑{-1})v&≡(\exists w)(uR↓2↑{-1}w\wedge wR↓1↑{-1}v)≡
(\exists w)(wR↓2u\wedge vR↓1w)\,.\cr}$$

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(R↓1\circ R↓2)\circ R↓3=R↓1\circ(R↓2\circ R↓3)$
(associativity of composition). This lets us write $R↓1\circ R↓2\circ R↓3$
without ambiguity.

\smallskip
Let $I↓S$ be the relation (on any set containing $S$) $uI↓Sv≡(u=v\in S)$.
If $S$ is the whole universe under consideration, we use~$I$, omitting
the subscript. This is the same relation as $=\,$, but avoids such
notational confusions as $=\circ =↑{-1}$.

If $R$ is a relation on $S$, define $R↑0=I↓S$, $R↑{i+1}=R↑i\circ R$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $R↑1=R$, $R↑{i+j}=R↑i\circ R↑j$, $(R↑i)↑j=R↑{ij}$,
$\hbox{\tt PARENT}↑3=\hbox{\tt GREATGRANDPARENT}$. Also define $R↑{-i}=(R↑{-1})↑i$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $R↑{-i}=(R↑i)↑{-1}$. Show $R↑i\circ R↑{-j}$ is not
always $R↑{i-j}$.

\smallskip
If $R↓1$ and $R↓2$ are relations from $S$ to $T$, define $R=R↓1\cup R↓2$ by 
$$uRv≡\bigl((uR↓1v)\vee (uR↓2v)\bigr)\,.$$
Similarly, if $R=R↓1\cap R↓2$,
$$uRv≡(uR↓1v\wedge uR↓2v)\,.$$

If $R↓1,R↓2,R↓3,\ldots$ is a finite or infinite sequence of relations,
$$\eqalign{R=\bigcup↓iR↓i&\quad\hbox{means}\quad uRv≡(\exists i)(uR↓iv)\cr
\noalign{\smallskip}
R=\bigcap↓iR↓i&\quad\hbox{means}\quad vRv≡(\forall i)(uR↓iv)\cr}$$

\smallskip
\disleft 38pt::
{\bf Drill:} Show 
$$\eqalign{(R↓1\cup R↓2)\cup R↓3&=R↓1\cup(R↓2\cup R↓3)\,,\cr
(R↓1\cap R↓2)\cap R↓3&=R↓1\cap(R↓2\cap R↓3)\,,\cr
R↓1\cap(R↓2\cup R↓3)&=(R↓1\cap R↓2)\cup(R↓1\cap R↓3)\,,\cr
R↓1\cup(R↓2\cap R↓3)&=(R↓1\cup R↓2)\cap(R↓1\cup R↓3)\,,\cr
R\cap\bigcup↓iR↓i&=\bigcup↓i(R\cap R↓i)\,,\cr
R\cup\bigcap↓iR↓i&=\bigcap↓i(R\cup R↓i)\,.\cr}$$

\smallskip
\disleft 38pt::
{\bf Answer:}
$$\eqalign{u\bigr((R↓1\cup R↓2)\cup R↓3)v&≡u(R↓1\cup R↓2)v\vee uR↓3v\cr
&≡\bigr((uR↓1v)\vee (uR↓2v)\bigr)\vee (uR↓3v)\cr
&≡(uR↓1v)\vee\bigr((uR↓2v)\vee(uR↓3v)\bigr)\,,\hbox{ etc.}\cr}$$

\smallskip
\disleft 38pt::
If $R$ is a relation on $S$, $R↑{\ast}$ is defined as $\bigcup↓{i≥0}R↑i$,
and $R↑+$ is $\bigcup↓{i≥1}R↑i$.

\smallskip
\disleft 38pt::
{\bf Drill:} $R↑{\ast}=I↓S\cup R↑+$, $R↑+=R\circ R↑{\ast}$, $I↓S↑{\ast}=I↓S$,
$(R\cup R↑i)↑{\ast}=R↑{\ast}$, $(R↑{\ast})↑{\ast}=R↑{\ast}$,
$\hbox{\tt PARENT}↑+=\hbox{\tt ANCESTOR}$, 
but not always $(R↑i)↑{\ast}=(R↑{\ast})↑i$.
If $R$ on the integers is $uRv≡(v=u+1)$, then $R↑{\ast}=$~``$≤$'' and
$R↑+=$~``$<$''.

\smallskip
A relation $R$ on $S$ is {\sl reflexive\/} if $(\forall u)(uRu)$, and
{\sl transitive\/} if $(uRv\wedge vRw)⊃(uRw)$. It is an
{\sl equivalence\/} (or RST) {\sl relation\/} if it is reflexive, symmetric,
and transitive.

%\vfill\eject

\smallskip
\disleft 38pt::
{\bf Drill:} Show $<\,$, $≤\,$, $\subseteq\,$, $\supset$ transitive,
$≠$ intransitive. Show $≤$ reflexive, $<$ irreflexive. Show $=\,$,
$\approx\,$, $≡↓M$ are all equivalence relations.

\smallskip
If $R$ is an equivalence relation on $S$, we can break $S$ up into disjoint
subsets $S↓1,S↓2,S↓3,\ldots$ (finitely or infinitely many) where 
$uRv≡(u$ and $v$ are in the same~$S↓i)$. The $S↓i$ are called the
{\sl equivalence classes\/} of~$R$. Use $[u]↓R$ to mean the equivalence
class to which $u$ belongs.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(uRv)≡([u]↓R=[v]↓R)$.
What are the equivalence classes of $≡↓2$?

\smallskip
If any set $S$ has a disjoint partition $\bigcup↓iS↓i$, show that there is an
equivalence relation $R$ on~$S$ of which the $S↓i$ are the equivalence classes.

\smallskip
\disleft 38pt::
\noindent{\bf Exercise.}
Show that, if $f$ is a function from set~$S$ to set~$T$, the relation
$R$ on~$S$ defined by $(xRy)\equiv \bigl(f(x)=f(y)\bigr)$ is an
equivalence relation. Conversely show that if $R$ is an equivalence
relation on a set~$S$, there is a set~$T$ and a function~$f$ from
$S$ to~$T$ such that $xRy$ if and only if $f(x)=f(y)$.



We may think of a relation $R$ from $S$ to $T$ as the set of
ordered pairs $\langle u,v\rangle$ for which $uRv$ is true.

\smallskip
\disleft 38pt::
{\bf Drill:} Show the previous definitions of $R↓1\cap R↓2$ and $R↓1\cup R↓2$
are consistent with this convention. Then $\emptyset$, the empty set,
is the always false relation; $u\emptyset v$ is false, $\emptyset\cap R=\emptyset$,
$\emptyset\cup R=R$. $S\times T$, as a relation from $S$ to~$T$, is always
true; $u(S\times T)v$ is true, $(S\times T)\cup R=S\times T$, 
$(S\times T)\cap R=R$. We can also say $R↓1\subseteq R↓2$ to mean
$uR↓1v⊃uR↓2v$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(R↓1\subseteq R↓2)≡(R↓1\cap R↓2=R↓1)≡(R↓1\cup R↓2=R↓2)$.

\smallskip
If $R$ is a relation from $S$ to $T$ and $p$ a property some relations have,
then the $p$-{\sl closure\/} of $R$ is the smallest relation $R'$ (if there
is one) such that $R\subseteq R'$ and $R'$ has property~$P$.
That is, $R'$ must include~$R$; it must have property~$p$; and it must
be a subset of any relation $R''$ that includes $R$ and has property~$p$.

The reflexive closure of $R$ on $S$ is $R\cup I↓S$; the symmetric closure
is $R\cup R↑{-1}$; the transitive closure is~$R↑+$; the reflexive transitive
closure is~$R↑{\ast}$; the equivalence (RST) closure is $(R\cup R↑{-1})↑{\ast}$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show the above.

\smallskip
Relations with finite domain and range may be displayed visually and stored
in a computer memory in several ways; for one, a table with rows indexed
by the elements of~$S$, columns by the elements of~$T$. The {\tt DIVIDES} relation,
on $(1:6)\times (0:8)$, is displayed by the table below:

$$\vbox{\tabskip=0pt\offinterlineskip
\halign{\rt{#}\quad&\vrule#&\strut\quad\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\vrule#\cr
&\omit&0&1&2&3&4&5&6&7&8&\omit\cr
&\multispan{11}\hrulefill\cr
&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
1&&X&X&X&X&X&X&X&X&X&\cr
2&&X&&X&&X&&X&&X&\cr
3&&X&&&X&&&X&&&\cr
4&&X&&&&X&&&&X&\cr
5&&X&&&&&X&&&&\cr
6&&X&&&&&&X&&&\cr
&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
&\multispan{11}\hrulefill\cr}}$$

\noindent
Such a table may be stored as a boolean array in a computer memory, and $uRv$
can be programmed as $R[u,v]$.

If $R$ is a relation on $S$, the table is square. If $R$ is reflexive, the
entire {\sl main diagonal\/} (from upper left to lower right) is marked;
if irreflexive, unmarked. If $R$ is symmetric, the table is symmetric around
the main diagonal. There is no simple visual test for transitivity. If
$R$ is an equivalence relation, the set $S$ can be placed in an order where
the marked regions of the table are squares covering the main diagonal:

$$\vbox{\tabskip=0pt\offinterlineskip
\halign{&\vrule#&\strut\quad\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\vrule#\cr
&\multispan{12}\hrulefill\cr
height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
&&X&X&X&X&&&&&&&\cr
&&X&X&X&X&&&&&&&\cr
&&X&X&X&X&&&&&&&\cr
&&X&X&X&X&&&&&&&\cr
&&&&&&X&&&&&&\cr
&&&&&&&X&X&&&&\cr
&&&&&&&X&X&&&&\cr
&&&&&&&&&X&&&\cr
&&&&&&&&&&X&&\cr
height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
&\multispan{12}\hrulefill\cr}}$$

\smallskip
\disleft 38pt::
{\bf Drill:} For which orderings of $S$ does the table take the form described?

\smallskip
A relation on $S$ may also be displayed as a {\sl directed graph\/} or
{\sl digraph}, a set~$S$ of {\sl nodes\/} and {\sl arcs}. The nodes are
normally shown as points,  small circles, boxes, or triangles. The
arcs, which are technically ordered pairs of nodes, are shown as arrows;
if $uRv$, there is an arrow from $u$ to~$v$. The nodes may be labeled with
their names. In such a graph, $uR↑{\ast}v$ iff there is a path from $u$
to $v$ following the arrows in their directions. If the relation is symmetric,
it is common to use a line without arrowheads between $u$ and~$v$ to show that
$uRv$; the digraph is then called a {\sl graph\/}, and the arcs {\sl edges\/}.

If a relation is reflexive, its digraph has {\sl loops\/}: arcs from each
node to itself.

It is possible to display several relations on $S$ in the same graph; each
arc is labeled with the name of the relation to which it belongs.

$$\vcenter{\halign{$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$\qquad
&$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$\qquad
&$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$\cr
&&<&&<&&<\cr
\noalign{\bigskip\bigskip}
&<&&<&&<&&<\cr
1&&2&&3&&4&&5\cr
\noalign{\bigskip\bigskip}
=&&=&&=&&=&&=\cr
\noalign{\bigskip\bigskip}
&&&<&&<\cr
\noalign{\bigskip\bigskip}
&&&&<\cr}}$$

\bigskip
We show the converse of a relation by reversing the arrows in its digraph.
We show its reflexive closure by filling in all loops.

\bigskip


%\bigskip
\noindent Paths in digraphs.
A {\sl path\/} from $q↓0$ to $q↓n$ is a sequence $\langle q↓0,x↓1,q↓1,\ldots,
x↓n,q↓n\rangle$ ($n≥0$) where $q↓{i-1}x↓iq↓i$ is an arc from $q↓{i-1}$ to~$q↓i$
labeled with~$x↓i$. 
The path is said to be {\sl labeled\/} with the concatenation
$x↓1x↓2\ldots x↓n$. The null path $\Lambda↓q$ from $q$ to~$q$ is the 
sequence~$\langle q\rangle$. The {\sl catenation\/} 
$p↓{qr}\aot p↓{rs}$ of a path $p↓{qr}$ from $q$ to~$r$ and a path $p↓{rs}$ from
$r$ to~$s$ is the concatenation $p↓{qr}\otimes\hbox{tail}(p↓{rs})$; notice
the elimination of the extra~$r$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(p↓{qr}\aot p↓{rs})\aot p↓{st}=p↓{qr}\aot (p↓{rs}\aot p↓{st})$.
Show $p↓{qr}\aot \Lambda↓r=p↓{qr}$; $\Lambda↓q\aot p↓{qr}=p↓{qr}$.
Show if $p↓{qr}$ is labeled with~$x$, and $p↓{rs}$ is labeled with~$y$,
$p↓{qr}\aot p↓{rs}$ is labeled with~$xy$.

\smallskip
\disleft 38pt::
{\bf Drill:} If $p↓{qr}$ is a path from $q$ to $r$ in a multirelation graph,
and $p↓{qr}$ is labeled with~$x$, and $x=\langle R↓1,R↓2,\ldots,R↓n\rangle$,
then $q(R↓1\circ R↓2\circ \cdots\circ R↓n)r$.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft July 2, 1984 

\vfill\eject

\noindent{\bf Course-of-Values Induction.}

\bigskip
To prove that a proposition $P(x)$ is true for all integers $x≥0$, a strategy
we may use is to assume $P(y)$ for {\sl any and all\/}~$y$ such that
$0≤y<x$, and prove $P(x)$ from this assumption. That is, we do not need
a separate basis step, and the induction step is allowed to assume not
just $P(x-1)$, but all of $P(0),P(1),P(2),\ldots,P(x-1)$. Nonetheless,
such a proof is valid, and is in fact a shorthand verson of a proof by
ordinary mathematical induction. To see why, 
define $Q(x)$ to mean the conjunction $(\forall y\mid 0≤y<x)P(y)$. To
prove $Q(x)$ by induction on~$x$, we first prove the basis step,
$Q(0)≡(\forall y\mid 0≤y<0)P(y)$. Since there are no such values of~$y$,
the basis step is true whatever $P$ is. 

The induction step requires assuming $Q(x)≡(\forall y\mid 0≤y<x)P(y)$, and
proving $Q(x+1)≡(\forall y\mid 0≤y<x+1)P(y)$, i.e., 
$(\forall y\mid 0≤y≤x)P(y)$, i.e., $(\forall y\mid 0≤y<x)P(y)∧P(x)$.
The first conjuct is~$Q(x)$, so we need only prove $P(x)$
from $(\forall y\mid 0≤y<x)P(y)$, the course-of-values induction step.
This proves $\forall x\,Q(x)$, which implies $Q(x+1)$, which
implies~$P(x)$, which is what we wanted to do. The technique of
proving $P(x)$ by assuming $P(y)$ for all $y<x$ is called course-of-values
induction.

\bigskip
\noindent{\bf Example:} [RWF: $a\in {\bf N}$, $b\in {\bf N}↓+$,
$q,r\in {\bf N}$]

If $a$ is an integer $≥0$, and $b>0$, there are unique numbers $q$ and~$r$
for which $a=bq+r$, $0≤r<b$. 

{\bf Case 1.} $a<b$. Then the only possibility is $q=0$, $r=a$.

{\bf Case 2.} $a≥b$. Let $a'=a-b≥0$. By course-of-values induction,
there are numbers $q'$, $r'$ with $a'=q'b+r'$, so $a=a'+b=(q'+1)b+r'$,
$q=q'+1$, $r=r'$.

\medskip
If there were any other values $q''$, $r''$ with $a=bq''+r''$, we could
have $a'=a-b=b(q''-1)+r''$, contrary to the course-of-values induction
assumption that $q'=q-1$, $r'=r$ are unique.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\bye

An NFA with finite alphabet $\Sigma$ and finite state set $Q$ is a labeled
digraph on $Q$ labeled with~$\Sigma$. It has a set of initial states,
$Q↓-\subseteq Q$, and a set of accepting states, $Q↓+\subseteq Q$; the
nodes are accordingly labeled with $+\,$, $-\,$ or both.

If $M$ is an NFA, it {\sl accepts\/} $x\in\Sigma↑{\ast}$ iff there is a
path in $M$ from a node in $Q↓-$ to a node in $Q↓+$ labeled with~$x$.

\bigskip

\hrule

\bigskip
\ctrline{**** RWF: This goes after set-relation composition.}

Let MALE be the set of humans (living or dead) who are male. Then
$\hbox{MALE}\circ\hbox{SIBLING}$ is BROTHER, and 
$\hbox{MALE}\circ\hbox{PARENT}↑{-1}$
is SON. We can associate with the set~$S$ its {\sl filter\/}~$I↓s$;
then $I↓{S↓1\cap S↓2}=I↓{S↓1}\cap I↓{S↓2}=I↓{S↓1}\circ I↓{S↓2}$. To
restrict a relation~$R$ to pairs $\langle u,v\rangle$ where
$u\in S↓1$, $v\in S↓2$, we can write $I↓{S↓1}\circ R\circ I↓{S↓2}$;
the father-daughter relation is 
$\hbox{MALE}\circ\hbox{PARENT}\circ\hbox{FEMALE}$.

\smallskip
{\bf Drill:} $I↓{S↓1}\circ I↓{S↓2}=I↓{S↓2}\circ I↓{S↓1}$. Notice that
$S\circ R$ can be considered a short form of $I↓S\circ R$, and $S↓1\circ S↓2$
a short form of $I↓{S↓1}\circ I↓{S↓2}=\emptyset$.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft July 2, 1984 

\bye